package arithmetic1.sort;

import java.util.Arrays;

/*
    快速排序算法
 */
public class QuickSort {
    public static void main(String[] args) {
//        int arr[]={15,6,7,43,5,1,67,8};
//        int arr[] = {8, 8, 7, 43, 5, 1, 67, 8};
        int[] arr = {2, 0, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    //快速排序算法
    public static void quickSort(int arr[], int start, int end) {
        //当数组元素大于等于2时才需要排序
        if (start < end) {
            //找到i
            int i = partition(arr, start, end);
            //将两个数组分别再分组
            quickSort(arr, start, i - 1);
            quickSort(arr, i + 1, end);
        }
    }

    //对数组划分
    public static int partition(int arr[], int start, int end) {
        int i = start;
        int j = end;
        //将第一个数作为参考
        int temp = arr[i];
        while (i != j) {
            //从右到左扫描第一个小于temp的数，将其放到坐边
            while (i < j && arr[j] >= temp) {
                j--;
            }
            arr[i] = arr[j];
            //从左向右扫描第一个大于temp的数，将其放到右边
            while (i < j && arr[i] <= temp) {
                i++;
            }
            arr[j] = arr[i];
        }
        //将temp放在中间
        arr[i] = temp;
        return i;
    }
}
